package com.example.demo.sort;

import java.util.Arrays;

public class SortPra {
    public static void main(String[] args) {
        int[] arr1 = new int[]{2, 3, 6, 8, 1, 4, 5, 7};
        mergeSort(arr1, 0, arr1.length - 1);
        System.out.println(Arrays.toString(arr1));
    }

    private static void mergeSort(int[] arr1, int s, int e) {
        int mid = (s + e) / 2;
        if (s < e) {
            mergeSort(arr1, s, mid);
            mergeSort(arr1, mid + 1, e);
            merge(arr1, s, mid, e);
        }
    }


    private static void merge(int[] arr1, int s, int e, int mid) {
        int l = s;
        int r = mid + 1;
        int i = 0;
        int tem[] = new int[(e - s) + 1];
        while (l < mid && r < e) {
            if (arr1[l] < arr1[r]) {
                tem[i++] = arr1[l++];
            } else {
                tem[i++] = arr1[r++];
            }
        }
        while (l < mid) {
            tem[i++] = arr1[l++];
        }
        while (r < e) {
            tem[i++] = arr1[r++];
        }
        for (int j = 0; j < tem.length; j++) {
            arr1[s + j] = tem[j];
        }
    }


    /**
     * 归并练习
     * 合并两个有序数据
     * int[] arr1 = new int[] { 2, 3, 6, 8 };
     * int[] arr2 = new int[] { 1, 4, 5, 7 };
     * int tem[] = new int[arr1.length+arr2.length];
     * merge(arr1,arr2,tem);
     * System.out.println(Arrays.toString(tem));
     */
    private static void merge(int[] arr1, int[] arr2, int[] tem) {
        int l = 0;
        int r = 0;
        int k = 0;
        while (l < arr1.length && r < arr2.length) {
            if (arr1[l] < arr2[r]) {
                tem[k++] = arr1[l++];
            } else {
                tem[k++] = arr2[r++];
            }
        }
        while (l < arr1.length) {
            tem[k++] = arr1[l++];
        }
        while (r < arr2.length) {
            tem[k++] = arr1[r++];
        }
    }


}
